package com.benben;

/**
 * 排序算法集合
 * 
 * @author fangming 2015年8月6日
 */
public class SortFactory {

	/**
	 * 冒泡排序--一般算法
	 */
	public static void bubbleSort(int[] array) {
		int temp;
		int len = array.length;
		for (int i = 0; i < len - 1; i++) { // 外层循环：每循环一次就确定了一个相对最大元素
			for (int j = 1; j < len - i; j++) { // 内层循环：有i个元素已经排好，根据i确定本次的比较次数
				if (array[j - 1] > array[j]) { // 如果前一位大于后一位，交换位置
					temp = array[j - 1];
					array[j - 1] = array[j];
					array[j] = temp;
				}
			}
			System.out.print("第" + (i + 1) + "轮排序结果：");
			display(array);
		}
	}

	/**
	 * 冒泡排序改进
	 * 
	 * @param array
	 */
	public static void bubbleSort1(int[] array) {
		int temp;
		int low = 0;
		int high = array.length - 1;
		int counter = 1;
		while (low < high) {
			for (int i = low; i < high; ++i) { // 正向冒泡，确定最大值
				if (array[i] > array[i + 1]) { // 如果前一位大于后一位，交换位置
					temp = array[i];
					array[i] = array[i + 1];
					array[i + 1] = temp;
				}
			}
			--high;
			for (int j = high; j > low; --j) { // 反向冒泡，确定最小值
				if (array[j] < array[j - 1]) { // 如果前一位大于后一位，交换位置
					temp = array[j];
					array[j] = array[j - 1];
					array[j - 1] = temp;
				}
			}
			++low;

			System.out.print("第" + counter + "轮排序结果：");
			display(array);
			counter++;
		}
	}

	/**
	 * 选择排序
	 * 
	 * @param array
	 */
	public static void selectSort(int[] array) {
		int minPoint; // 存储最小元素的小标
		int len = array.length;
		int temp;
		int counter = 1;

		for (int i = 0; i < len - 1; i++) {

			minPoint = i;
			// 每完成一轮排序，就确定了一个相对最小元素，下一轮排序只对后面的元素排序
			for (int j = i + 1; j <= len - 1; j++) {
				// 如果待排数组中的某个元素比当前元素小，minPoint指向该元素的下标
				if (array[j] < array[minPoint]) {
					minPoint = j;
				}
			}
			// 如果发现了更小的元素，交换位置
			if (minPoint != i) {
				temp = array[i];
				array[i] = array[minPoint];
				array[minPoint] = temp;
			}
			System.out.print("第" + counter + "轮排序结果：");
			display(array);
			counter++;
		}
	}

	/**
	 * 选择排序改进
	 * 
	 * @param array
	 */
	public static void selectSort1(int[] array) {
		int minPoint; // 存储最小元素的小标
		int maxPoint; // 存储最大元素的小标
		int len = array.length;
		int temp;
		int counter = 1;
		for (int i = 0; i < len / 2; i++) {
			minPoint = i;
			maxPoint = i;
			// 每完成一轮排序，就确定了两个最值，下一轮排序时比较范围减少两个元素
			for (int j = i + 1; j <= len - 1 - i; j++) {
				// 如果待排数组中的某个元素比当前元素小，minPoint指向该元素的下标
				if (array[j] < array[minPoint]) {
					minPoint = j;
					continue;
					// 如果待排数组中的某个元素比当前元素大，maxPoint指向该元素的下标
				} else if (array[j] > array[maxPoint]) {
					maxPoint = j;
				}
			}
			// 如果发现了更小的元素，与第一个元素交换位置
			if (minPoint != i) {
				temp = array[i];
				array[i] = array[minPoint];
				array[minPoint] = temp;
				// 原来的第一个元素已经与下标为minPoint的元素交换了位置
				// 如果之前maxPoint指向的是第一个元素，那么需要将maxPoint重新指向array[minPoint]
				// 因为现在array[minPoint]存放的才是之前第一个元素中的数据
				if (maxPoint == i) {
					maxPoint = minPoint;
				}
			}
			// 如果发现了更大的元素，与最后一个元素交换位置
			if (maxPoint != len - 1 - i) {
				temp = array[len - 1 - i];
				array[len - 1 - i] = array[maxPoint];
				array[maxPoint] = temp;
			}

			System.out.print("第" + counter + "轮排序结果：");
			display(array);
			counter++;
		}
	}

	/**
	 * 插入排序
	 * @param array
	 */
	public static void insertSort(int[] array) {
		int len = array.length;
		int counter = 1;
		for (int i = 1; i < len; i++) {
			int temp = array[i]; // 存储待排序的元素值
			int insertPoint = i - 1; // 与待排序元素值作比较的元素的下标
			while (insertPoint >= 0 && array[insertPoint] > temp) { // 当前元素比待排序元素大
				array[insertPoint + 1] = array[insertPoint]; // 当前元素后移一位
				insertPoint--;
			}
			array[insertPoint + 1] = temp; // 找到了插入位置，插入待排序元素
			System.out.print("第" + counter + "轮排序结果：");
			display(array);
			counter++;
		}
	}
	
	/**
	 *  二分插入排序
	 * @param array
	 */
	public static void binaryInsertSort(int[] array) {
		int len = array.length;
		int counter = 1;
		
		for (int i = 1; i < len; i++) {
			int temp = array[i]; // 存储待排序的元素值
			if (array[i - 1] > temp) { // 比有序数组的最后一个元素要小
				int insertIndex = binarySearch(array, 0, i - 1, temp); // 获取应插入位置的下标
				for (int j = i; j > insertIndex; j--) { // 将有序数组中，插入点之后的元素后移一位
					array[j] = array[j - 1];
				}
				array[insertIndex] = temp; // 插入待排序元素到正确的位置
			}

			System.out.print("第" + counter + "轮排序结果：");
			display(array);
			counter++;
		}
	}

	/**
	 * 二分查找法,返回索引
	 * @param array
	 * @param lowerBound
	 * @param upperBound
	 * @param target
	 * @return 索引
	 */
	public static int binarySearch(int[] array, int lowerBound, int upperBound, int target) {
		int curIndex = 0;
		while (lowerBound <= upperBound) {
			curIndex = (lowerBound + upperBound) / 2;
			if (array[curIndex] > target) {
				upperBound = curIndex - 1;
			} else {
				lowerBound = curIndex + 1;
			}
		}
		return lowerBound;
	}
	
	// 按顺序打印数组中的元素
	private static void display(int[] array) {
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + "\t");
		}
		System.out.println();
	}
}
